home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / CTOOLS10.ARJ / AVL.H < prev    next >
C/C++ Source or Header  |  1991-12-31  |  3KB  |  105 lines
  1. /****************************************************************************
  2. *
  3. *                    Copyright (C) 1991 Kendall Bennett.
  4. *                            All rights reserved.
  5. *
  6. * Filename:        $RCSfile: avl.h $
  7. * Version:        $Revision: 1.3 $
  8. *
  9. * Language:        ANSI C
  10. * Environment:    any
  11. *
  12. * Description:    Header file for AVL tree module.
  13. *
  14. * $Id: avl.h 1.3 91/12/31 19:41:40 kjb Exp $
  15. *
  16. * Revision History:
  17. * -----------------
  18. *
  19. * $Log:    avl.h $
  20. * Revision 1.3  91/12/31  19:41:40  kjb
  21. * Modified include file directories.
  22. * 
  23. * Revision 1.2  91/09/27  03:11:19  kjb
  24. * Added compatibility with C++.
  25. * 
  26. * Revision 1.1  91/09/27  02:50:21  kjb
  27. * Initial revision
  28. * 
  29. ****************************************************************************/
  30.  
  31. #ifndef    __AVL_H
  32. #define    __AVL_H
  33.  
  34. #ifndef    __DEBUG_H
  35. #include "debug.h"
  36. #endif
  37.  
  38. /*---------------------- Macros and type definitions ----------------------*/
  39.  
  40. typedef struct AVL_BUCKET {
  41.     struct AVL_BUCKET    *left;        /* Pointer to left subtree            */
  42.     struct AVL_BUCKET    *right;        /* Pointer to right subtree            */
  43.     short                bal;        /* Balance factor                    */
  44.     } AVL_BUCKET;
  45.  
  46. typedef struct {
  47.     int            count;            /* Number of elements currently in tree    */
  48.     int            (*cmp)(void*,void*);    /* Compare two nodes            */
  49.     AVL_BUCKET    *root;            /* Pointer to root node of AVL tree        */
  50.     } AVL_TREE;
  51.  
  52. /* The three traversal orders supported    */
  53.  
  54. #define    PREORDER    0
  55. #define    INORDER        1
  56. #define    POSTORDER    2
  57.  
  58. #define    MAXLEVEL    64            /* Maximum levels for avl_print            */
  59.  
  60. /* The three balance factors stored in each subtree                        */
  61.  
  62. #define    LH        0                /* Left subtree is larger                */
  63. #define    BAL        1                /* Subtree is balanced                    */
  64. #define    RH        2                /* Right subtree is balanced            */
  65.  
  66. /* Return a pointer to the user space given the address of the header of
  67.  * a node.
  68.  */
  69.  
  70. #define    AVL_USERSPACE(h)    ((void*)((AVL_BUCKET*)(h) + 1))
  71.  
  72. /* Return a pointer to the header of a node, given the address of the
  73.  * user space.
  74.  */
  75.  
  76. #define    AVL_HEADER(n)        ((AVL_BUCKET*)(n) - 1)
  77.  
  78. #define    AVL_EMPTY(t)        ((t)->count == 0)
  79.  
  80. /*-------------------------- Function Prototypes --------------------------*/
  81.  
  82. #ifdef __cplusplus
  83. extern "C" {
  84. #endif
  85.  
  86. void *avl_newnode(int size);
  87. void avl_freenode(void *node);
  88. AVL_TREE *avl_init(int (*cmp_function)());
  89. void avl_empty(AVL_TREE *t,void (*freeNode)());
  90. void *avl_insert(AVL_TREE *tree,void *node);
  91. void *avl_delete(AVL_TREE *tree,void *node);
  92. void avl_traverse(AVL_TREE *tree,int order,void (*visit)(),void *params);
  93. void avl_print(FILE *out,AVL_TREE *tree,void (*prnt)(),bool graph_chars);
  94. void *avl_findsym(AVL_TREE *tree,void *node);
  95. void avl_range(AVL_TREE *tree,void *lower,void *upper,void (*visit)(),
  96.     void *params);
  97. void *avl_delmin(AVL_TREE *tree);
  98. void *avl_delmax(AVL_TREE *tree);
  99.  
  100. #ifdef __cplusplus
  101. }
  102. #endif
  103.  
  104. #endif
  105.